
<TITLE>prob006: Golomb rulers</TITLE>
<HR><!------------------------------------------------------------------------>
<CENTER>
<H1>prob006: Golomb rulers</H1>

<TABLE>
<TR> <TD> proposed by
     <TD ALIGN=LEFT> <A HREF="http://www.cs.ualberta.ca/~vanbeek">
          <B>Peter van Beek</B></A> 
          <ADDRESS><a href="mailto:vanbeek@cs.ualberta.ca">
          vanbeek@cs.ualberta.ca</a></ADDRESS>
</TABLE>
</CENTER>

<HR><!------------------------------------------------------------------------>
<H3> Specification </H3>

<TT>

These problems are said to have many practical applications including
sensor placements for x-ray crystallography and radio astronomy.
A Golomb ruler may be defined as a set of m integers
0 = a_1 < a_2 < ... < a_m such that the m(m-1)/2 differences
a_j - a_i, 1 <= i < j <= m are distinct. Such a ruler is said
to contain m marks and is of length a_m. The objective is to 
find optimal (minimum length) or near optimal rulers.

<P>

Note that a symmetry can be removed by adding the 
constraint that a_2 - a_1 < a_m - a_{m-1}, the first difference is
less than the last. 

<P>

There exist several interesting generalizations of the problem
which have received attention like modular Golomb rulers (differences
are all distinct mod a given base), disjoint Golomb rulers, 
Golomb rectangles (the 2-dimensional generalization of Golomb rulers),
and difference triangle sets (sets of rulers with no common difference). 

</TT>

<P>
<HR><!------------------------------------------------------------------------>

<UL>

 <A HREF="../../index.html"> Back</A> to CSPLib home page.


